package tree;

import java.util.ArrayList;
import java.util.List;

public class LeetCode95DP {
    public static List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        if (n == 0) {
            return dp[0];
        }

        dp[0].add(null);

        for (int i = 1; i <= n; i++) {
            dp[i] = new ArrayList<>();
            for (int j = 1; j <= i; j++) {
                for (TreeNode left : dp[j - 1]) {
                    for (TreeNode right : dp[i - j]) {
                        TreeNode root = new TreeNode(j);
                        root.left = left;
                        root.right = cloneTree(right, j);
                        dp[i].add(root);
                    }
                }
            }
        }

        return dp[n];
    }

    public static TreeNode cloneTree(TreeNode node, int offset) {
        if (node == null) {
            return null;
        }
        TreeNode newNode = new TreeNode(node.val + offset);
        newNode.left = cloneTree(node.left, offset);
        newNode.right = cloneTree(node.right, offset);
        return newNode;
    }

    // Helper function to print trees (preorder traversal)
    public static void printTrees(List<TreeNode> trees) {
        for (TreeNode root : trees) {
            printTree(root);
            System.out.println();
        }
    }

    public static void printTree(TreeNode root) {
        if (root == null) {
            System.out.print("null ");
            return;
        }
        System.out.print(root.val + " ");
        printTree(root.left);
        printTree(root.right);
    }

    public static void main(String[] args) {
        int n = 3;
        List<TreeNode> result = generateTrees(n);
        printTrees(result);
    }
}